﻿// 4312. 出现次数.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
/*
https://www.acwing.com/problem/content/4315/

给定一个长度为 n
 的字符串 S=s1s2…sn
 以及一个长度为 m
 的字符串 T=t1t2…tm
。

两个字符串都由小写字母构成。

用 s[l,r]
 来表示字符串 S
 的子串 slsl+1…sr
。

有 q
 个询问，每个询问给出两个整数 li,ri
（1≤li≤ri≤n
），请你计算字符串 T
 在 s[li,ri]
 中作为子串出现了多少次。

例如，字符串 abacabadabacaba 中共包含 4
 个子串 ba，所以 ba 在 abacabadabacaba 中作为子串出现了 4
 次。

输入格式
第一行包含三个整数 n,m,q
。

第二行包含一个长度为 n
 的由小写字母构成的字符串 S
。

第三行包含一个长度为 m
 的由小写字母构成的字符串 T
。

接下来 q
 行，每行包含两个整数 li,ri
。

输出格式
每个询问输出一行答案，一个整数，表示出现次数。

数据范围
前三个测试点满足 1≤n,m,q≤20
。
所有测试点满足 1≤n,m≤1000
，1≤q≤105
，1≤li≤ri≤n
。

输入样例1：
15 2 3
abacabadabacaba
ba
1 15
3 4
2 14
输出样例1：
4
0
3
输入样例2：
3 5 2
aaa
baaab
1 3
1 1
输出样例2：
0
0
*/
#include <iostream>

int main()
{
    std::cout << "Hello World!\n";
}

 